import java.util.LinkedList;

public class Node
{
	Node				parent;
	LinkedList<Node>	children		= new LinkedList<Node>();
	State				currentState;
	String				currentMovement;							// operator
																	// used
	// this list includes the current movemnt
	LinkedList<String>	movementsSoFar	= new LinkedList<String>();
	int					Level;
	Block				blocktoBeMoved;
	int					score;

	public Node()
	{
		super();
	}

	public Node(Node parent, LinkedList<Node> children,
			LinkedList<String> movementsSoFar, int level,
			String currentMovement, State currentState, Block blocktoBeMoved)
	{
		super();
		this.parent = parent;
		this.children = children;
		this.movementsSoFar = movementsSoFar;
		this.Level = level;
		this.currentMovement = currentMovement;
		this.currentState = currentState;
		this.blocktoBeMoved = blocktoBeMoved;
		score = this.Level; // any node is undesirable to be expanded first unless
						// otherwise is stated
	}

	public Node getParent()
	{
		return parent;
	}

	public void setParent(Node parent)
	{
		this.parent = parent;
	}

	public LinkedList<Node> getChildren()
	{
		return children;
	}

	public void setChildren(LinkedList<Node> children)
	{
		this.children = children;
	}

	public LinkedList<String> getMovementsSoFar()
	{
		return movementsSoFar;
	}

	public void setMovementsSoFar(LinkedList<String> movementsSoFar)
	{
		this.movementsSoFar = movementsSoFar;
	}

	public int getLevel()
	{
		return Level;
	}

	public void setLevel(int level)
	{
		Level = level;
	}

	public String getCurrentMovement()
	{
		return currentMovement;
	}

	public void setCurrentMovement(String currentMovement)
	{
		this.currentMovement = currentMovement;
	}

	public Block getBlocktoBeMoved()
	{
		return blocktoBeMoved;
	}

	public void setBlocktoBeMoved(Block blocktoBeMoved)
	{
		this.blocktoBeMoved = blocktoBeMoved;
	}

	public State getCurrentState()
	{
		return currentState;
	}

	public void setCurrentState(State currentState)
	{
		this.currentState = currentState;
	}

	public int getScore()
	{
		return score;
	}

	public void setScore(int score)
	{
		this.score = score;
	}

	/**
	 * method to check if the node is the node at which the state is the goal
	 * state
	 * 
	 * @param exploredNode
	 * @return
	 */
	public boolean isGoal(Node exploredNode)
	{

		if (exploredNode.getCurrentState().getCurrentBoard().getBlock(2, 5) != null
				&& exploredNode.getCurrentState().getCurrentBoard()
						.getBlock(2, 5).getBlockNumber() == 0)
		{
			return true;
		}
		return false;
	}

	public LinkedList<Pair> getSpaces(State currentState)
	{
		Board currentBoard = currentState.getCurrentBoard();
		LinkedList<Pair> emptySpace = new LinkedList<Pair>();

		for (int row = 0; row < 6; row++)
		{
			for (int coloumn = 0; coloumn < 6; coloumn++)
			{
				if (currentBoard.getBlock(row, coloumn) == null)
				{
					emptySpace.add(new Pair(row, coloumn));
				}
			}
		}
		return emptySpace;
	}

	public LinkedList<Node> insertInList(Node toBeExpanded)
	{
		Pair emptySpace;

		LinkedList<Pair> currentSpaces = getSpaces(toBeExpanded
				.getCurrentState());

		while (!currentSpaces.isEmpty())
		{
			emptySpace = currentSpaces.pop();

			if (checkIfCanMoveDown(toBeExpanded.getCurrentState(), emptySpace))
			{
				moveDown(toBeExpanded, emptySpace);
			}
			if (checkIfCanMoveUp(toBeExpanded.getCurrentState(), emptySpace))
			{
				moveUp(toBeExpanded, emptySpace);
			}

			if (checkIfCanMoveLeft(toBeExpanded.getCurrentState(), emptySpace))
			{
				moveLeft(toBeExpanded, emptySpace);
			}
			if (checkIfCanMoveRight(toBeExpanded.getCurrentState(), emptySpace))
			{
				moveRight(toBeExpanded, emptySpace);
			}

		}
       
		return toBeExpanded.getChildren();

	}

	public Boolean checkIfCanMoveDown(State stateBeforeMovement, Pair emptySpace)
	{

		if (emptySpace.getX() - 1 > -1
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX() - 1, emptySpace.getY()) != null
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX() - 1, emptySpace.getY()).state == 'V')
		{

			return true;

		}
		return false;
	}

	public Boolean checkIfCanMoveUp(State stateBeforeMovement, Pair emptySpace)
	{

		if (emptySpace.getX() + 1 < 6
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX() + 1, emptySpace.getY()) != null
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX() + 1, emptySpace.getY()).state == 'V')
		{


			return true;
		}
		return false;
	}

	public Boolean checkIfCanMoveLeft(State stateBeforeMovement, Pair emptySpace)
	{
		if (emptySpace.getY() + 1 < 6
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX(), emptySpace.getY() + 1) != null
				&& (stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX(), emptySpace.getY() + 1).state == 'H' || stateBeforeMovement
						.getCurrentBoard().getBlock(emptySpace.getX(),
								emptySpace.getY() + 1).state == 'M'))
		{

			return true;
		}
		return false;
	}

	public Boolean checkIfCanMoveRight(State stateBeforeMovement,
			Pair emptySpace)
	{

		if (emptySpace.getY() - 1 > -1
				&& stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX(), emptySpace.getY() - 1) != null
				&& (stateBeforeMovement.getCurrentBoard().getBlock(
						emptySpace.getX(), emptySpace.getY() - 1).state == 'H' || stateBeforeMovement
						.getCurrentBoard().getBlock(emptySpace.getX(),
								emptySpace.getY() - 1).state == 'M'))
		{
			return true;
		}
		return false;
	}

	public void moveUp(Node toBeExpanded, Pair emptySpace)
	{

		LinkedList<Node> mychildren = new LinkedList<Node>();
		int emptyR = emptySpace.getX();
		int emptyC = emptySpace.getY();

		LinkedList<String> movSoFar = copyLinkedList(toBeExpanded);
		movSoFar.addLast("Up");

		// creation of a new Board
		Board temp = toBeExpanded.getCurrentState().getCurrentBoard()
				.copyBoard(toBeExpanded.getCurrentState().getCurrentBoard());
		State myCurrentState = new State(temp);

		// create a pair && a block that is going to move
		Pair newLocation = new Pair(emptyR, emptyC);
		LinkedList<Pair> tempList = new LinkedList<Pair>();
		Block tempBlock = temp.getBlock(emptyR + 1, emptyC);
		tempList = copyLinkedListOfPairs(tempBlock);
		tempList.removeLast();
		tempList.addFirst(newLocation);

		// creating a new block to add it to board
		Block toBeMoved = new Block(tempBlock.getState(), tempList,
				tempBlock.getBlockNumber());

		// this condition is to check whether the block occupies 3 places or 2
		if (emptyR + 3 < 6 
				&& temp.getBlock(emptyR + 3, emptyC) != null
				&& temp.getBlock(emptyR + 1, emptyC).blockNumber == temp
						.getBlock(emptyR + 3, emptyC).blockNumber)
		{
			//System.out.println("true");
			// removing the old block
			myCurrentState.getCurrentBoard().removeBlock(emptyR + 3, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR + 2, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR + 1, emptyC);

			// adding the new block to the board
			myCurrentState.getCurrentBoard()
					.addBlock(emptyR, emptyC, toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR + 1, emptyC,
					toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR + 2, emptyC,
					toBeMoved);
		}
		else
		{
			//System.out.println(myCurrentState.getCurrentBoard().getBlock(emptyR + 2, emptyC).getBlockNumber());
			// removing the old block
			myCurrentState.getCurrentBoard().removeBlock(emptyR + 2, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR + 1, emptyC);

			// adding the new block to the board
			myCurrentState.getCurrentBoard()
					.addBlock(emptyR, emptyC, toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR + 1, emptyC,
					toBeMoved);
		}
		int lev = toBeExpanded.getLevel();
		Node NodeMovingUp = new Node(toBeExpanded, mychildren, movSoFar,
				lev + 1, "Up", myCurrentState, toBeMoved);
		if(!(NodeMovingUp.getParent().getCurrentMovement().equals("Down")&& NodeMovingUp.getParent().getBlocktoBeMoved().getBlockNumber()==NodeMovingUp.getBlocktoBeMoved().getBlockNumber()))

		toBeExpanded.children.addLast(NodeMovingUp);
	}

	public void moveDown(Node toBeExpanded, Pair emptySpace)
	{

		
		LinkedList<Node> mychildren = new LinkedList<Node>();
		int emptyR = emptySpace.getX();
		int emptyC = emptySpace.getY();

		LinkedList<String> movSoFar = copyLinkedList(toBeExpanded);
		movSoFar.addLast("Down");

		// creation of a new Board
		Board temp = toBeExpanded.getCurrentState().getCurrentBoard()
				.copyBoard(toBeExpanded.getCurrentState().getCurrentBoard());
		State myCurrentState = new State(temp);

		// create a pair && a block that is going to move
		Pair newLocation = new Pair(emptyR, emptyC);
		LinkedList<Pair> tempList = new LinkedList<Pair>();
		Block tempBlock = temp.getBlock(emptyR - 1, emptyC);
		tempList = copyLinkedListOfPairs(tempBlock);
		tempList.removeFirst();
		tempList.addLast(newLocation);

		// creating a new block to add it to board
		Block toBeMoved = new Block(tempBlock.getState(), tempList,
				tempBlock.getBlockNumber());

		// this condition is to check whether the block occupies 3 places or 2
		if (emptyR - 3 > -1
				&& temp.getBlock(emptyR - 3, emptyC) != null
				&& temp.getBlock(emptyR - 1, emptyC).blockNumber == temp
						.getBlock(emptyR - 3, emptyC).blockNumber)
		{
			// removing the old block
			myCurrentState.getCurrentBoard().removeBlock(emptyR - 3, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR - 2, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR - 1, emptyC);

			// adding the new block to the board
			myCurrentState.getCurrentBoard()
					.addBlock(emptyR, emptyC, toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR - 1, emptyC,
					toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR - 2, emptyC,
					toBeMoved);
		}
		else
		{
			// removing the old block
			myCurrentState.getCurrentBoard().removeBlock(emptyR - 2, emptyC);
			myCurrentState.getCurrentBoard().removeBlock(emptyR - 1, emptyC);

			// adding the new block to the board
			myCurrentState.getCurrentBoard()
					.addBlock(emptyR, emptyC, toBeMoved);

			myCurrentState.getCurrentBoard().addBlock(emptyR - 1, emptyC,
					toBeMoved);
		}

		Node NodeMovingDown = new Node(toBeExpanded, mychildren, movSoFar,
				toBeExpanded.getLevel() + 1, "Down", myCurrentState, toBeMoved);
		if(!(NodeMovingDown.getParent().getCurrentMovement().equals("Up")&& NodeMovingDown.getParent().getBlocktoBeMoved().getBlockNumber()==NodeMovingDown.getBlocktoBeMoved().getBlockNumber()))

		toBeExpanded.children.addLast(NodeMovingDown);
	}

	public void moveRight(Node toBeExpanded, Pair emptySpace)
	{

		
		LinkedList<Node> mychildren = new LinkedList<Node>();
		int emptyR = emptySpace.getX();
		int emptyC = emptySpace.getY();

		LinkedList<String> movSoFar = copyLinkedList(toBeExpanded);
		movSoFar.addLast("Right");

		// creation of a new Board
		Board temp = toBeExpanded.getCurrentState().getCurrentBoard()
				.copyBoard(toBeExpanded.getCurrentState().getCurrentBoard());
		State myCurrentState = new State(temp);

		// create a pair && a block that is going to move
		Pair newLocation = new Pair(emptyR, emptyC);
		LinkedList<Pair> tempList = new LinkedList<Pair>();

		Block tempBlock = temp.getBlock(emptyR, emptyC - 1);
		tempList = copyLinkedListOfPairs(tempBlock);
		tempList.removeFirst();
		tempList.addLast(newLocation);

		// creating a new block to add it to board
		Block toBeMoved = new Block(tempBlock.getState(), tempList,
				tempBlock.getBlockNumber());

		// removing the old block
		myCurrentState.getCurrentBoard().removeBlock(emptyR, emptyC - 2);
		myCurrentState.getCurrentBoard().removeBlock(emptyR, emptyC - 1);

		// adding the new block to the board
		myCurrentState.getCurrentBoard().addBlock(emptyR, emptyC, toBeMoved);

		myCurrentState.getCurrentBoard()
				.addBlock(emptyR, emptyC - 1, toBeMoved);

		// creating the node
		Node NodeMovingRight = new Node(toBeExpanded, mychildren, movSoFar,
				toBeExpanded.getLevel() + 1, "Right", myCurrentState, toBeMoved);
		if(!(NodeMovingRight.getParent().getCurrentMovement().equals("Left")&& NodeMovingRight.getParent().getBlocktoBeMoved().getBlockNumber()==NodeMovingRight.getBlocktoBeMoved().getBlockNumber()))
		toBeExpanded.getChildren().addLast(NodeMovingRight);

	}

	public void moveLeft(Node toBeExpanded, Pair emptySpace)
	{
		
		LinkedList<Node> mychildren = new LinkedList<Node>();
		int emptyR = emptySpace.getX();
		int emptyC = emptySpace.getY();

		LinkedList<String> movSoFar = copyLinkedList(toBeExpanded);
		movSoFar.addLast("Left");

		// creation of a new Board
		Board temp = toBeExpanded.getCurrentState().getCurrentBoard()
				.copyBoard(toBeExpanded.getCurrentState().getCurrentBoard());
		State myCurrentState = new State(temp);

		// create a pair && a block that is going to move
		Pair newLocation = new Pair(emptyR, emptyC);
		LinkedList<Pair> tempList = new LinkedList<Pair>();

		Block tempBlock = temp.getBlock(emptyR, emptyC + 1);
		tempList = copyLinkedListOfPairs(tempBlock);
		tempList.removeLast();
		tempList.addFirst(newLocation);

		// creating a new block to add it to board
		Block toBeMoved = new Block(tempBlock.getState(), tempList,
				tempBlock.getBlockNumber());

		// removing the old block
		myCurrentState.getCurrentBoard().removeBlock(emptyR, emptyC + 2);
		myCurrentState.getCurrentBoard().removeBlock(emptyR, emptyC + 1);

		// adding the new block to the board
		myCurrentState.getCurrentBoard().addBlock(emptyR, emptyC, toBeMoved);

		myCurrentState.getCurrentBoard()
				.addBlock(emptyR, emptyC + 1, toBeMoved);

		// creating the node
		
		Node NodeMovingLeft = new Node(toBeExpanded, mychildren, movSoFar,
				toBeExpanded.getLevel() + 1, "Left", myCurrentState, toBeMoved);
		if(!(NodeMovingLeft.getParent().getCurrentMovement().equals("Right")&& NodeMovingLeft.getParent().getBlocktoBeMoved().getBlockNumber()==NodeMovingLeft.getBlocktoBeMoved().getBlockNumber()))
		       toBeExpanded.getChildren().addLast(NodeMovingLeft);
	}

	public LinkedList<String> addListToList(LinkedList<String> movementsSoFar,
			LinkedList<String> PreviousMovement)
	{
		int size = PreviousMovement.size();
		for (int i = 0; i < size; i++)
		{
			movementsSoFar.addLast(PreviousMovement.pop());
		}
		return movementsSoFar;

	}

	public LinkedList<String> copyLinkedList(Node toBeExpanded)
	{
		LinkedList<String> toBeCopied = toBeExpanded.getMovementsSoFar();
		LinkedList<String> copy = new LinkedList<String>();
		for (int i = 0; i < toBeCopied.size(); i++)
		{
			copy.add(toBeCopied.get(i));
		}
		return copy;
	}

	public LinkedList<Pair> copyLinkedListOfPairs(Block b)
	{
		LinkedList<Pair> beta3 = b.getLocation();
		LinkedList<Pair> Rage3 = new LinkedList<Pair>();
		for (int i = 0; i < beta3.size(); i++)
		{
			Rage3.add(beta3.get(i));
		}
		return Rage3;
	}

	public static void main(String[] args)
	{
		LinkedList<String> test = new LinkedList<String>();
		test.add("a");
		test.add("b");
		Node n = new Node();
		n.setMovementsSoFar(test);
		LinkedList<String> result = n.copyLinkedList(n);
		n.setBlocktoBeMoved(null);
		test.add("C");
		test.remove(0);
		for (int i = 0; i < 2; i++)
			System.out.println(result.get(i));
	}
}
